//给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。 
//
// 注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。 
//
// 返回一个表示每个字符串片段的长度的列表。 
//
// 
//示例 1：
//
// 
//输入：s = "ababcbacadefegdehijhklij"
//输出：[9,7,8]
//解释：
//划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
//每个字母最多出现在一个片段中。
//像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。 
//
// 示例 2： 
//
// 
//输入：s = "eccbbbbdec"
//输出：[10]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 500 
// s 仅由小写英文字母组成 
// 
//
// Related Topics 贪心 哈希表 双指针 字符串 👍 1083 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

//java:划分字母区间
public class Q0763PartitionLabels {
    public static void main(String[] args){
        Solution solution = new Q0763PartitionLabels().new Solution();
        solution.partitionLabels("ababcbacadefegdehijhklij");
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<Integer> partitionLabels(String s) {
        char[] charArr = s.toCharArray();
        // 每个字母开始结束下标集合
        int[][] indexArr = new int[26][2];
        // 记录已经遍历过字母的下标，下次遍历到跳过
        List<Integer> skipList = new ArrayList<>();
        for (int i = 0; i < charArr.length; i++) {
            if (skipList.contains(i)) continue;
            indexArr[charArr[i] - 'a'][0] = i;
            for (int j = i; j < charArr.length; j++) {
                if (charArr[i] == charArr[j]) {
                    indexArr[charArr[i] - 'a'][1] = j;
                    skipList.add(j);
                }
            }
        }
        List<int []> mergedArr = new ArrayList<>();

        // 有的字母没有就是[0,0],遍历时需要找最后一个
        Arrays.sort(indexArr, (o1, o2) -> o1[0] != o2[0] ? o1[0] - o2[0] : o1[1] - o2[1]);
        for (int i = 0; i < indexArr.length; i++) {
            if (i != indexArr.length - 1 && indexArr[i + 1][0] == 0) continue;
            // 取最大区间的经典写法
            int[] tempArr = new int[2];
            if (mergedArr.size() == 0 || mergedArr.get(mergedArr.size() - 1)[1] < indexArr[i][0]) {
                tempArr[0] = indexArr[i][0];
                tempArr[1]= indexArr[i][1];
                mergedArr.add(tempArr);
            } else {
                mergedArr.get(mergedArr.size() - 1)[1] = Math.max(mergedArr.get(mergedArr.size() - 1)[1], indexArr[i][1]);
            }
        }
        List<Integer> resList = mergedArr.stream().map(o -> o[1] - o[0] + 1).collect(Collectors.toList());
        return resList;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}